package edu.spbsu.nonsm00th.computgeom.chull.impl;

import edu.spbsu.nonsm00th.computgeom.chull.ConvexHull;
import edu.spbsu.nonsm00th.computgeom.util.D2Util;
import edu.spbsu.nonsm00th.computgeom.util.DNUtil;
import edu.spbsu.nonsm00th.model.Point;
import edu.spbsu.nonsm00th.model.enums.Orientation;
import edu.spbsu.nonsm00th.util.Precondition;
import java.util.ArrayList;
import java.util.List;

/**
 * Realization of Chan convex hull algorithm.
 * Should be used only for 2-dimensional point lists.
 * 
 * @author mbuzdov
 */
public class D2ChanConvexHull implements ConvexHull {

    private ConvexHull grahamConvexHull = new D2GrahamConvexHull();
    private Point min;

    public void convexHull(List<Point> list) {
        Precondition.argsNotNull(list);
        if (0 == list.size()) {
            return;
        }

        min = DNUtil.findCartesianMinimum(list);

        int n = list.size();
        int T = 1 == n ? 1 : 1 + (int)log2(log2(n));
        List<Point> result = null;
        for (int t = 1; t <= T; t++) {
            int M = (int)Math.pow(2, Math.pow(2, t));
            int m = Math.min(M, n);
            result = convexHull(list, m);
            if (null != result) {
                break;
            }
        }

        list.clear();
        list.addAll(result);
    }

    private List<Point> convexHull(List<Point> l, int m) {
        int groupsCount = l.size() / m;
        if (m * groupsCount < l.size()) {
            groupsCount += 1;
        }

        List<List<Point>> groups = new ArrayList<List<Point>>(groupsCount);
        for (int i = 0; i < groupsCount; i++) {
            int begin = i * m;//always less than l.size()
            int end = Math.min(l.size(), (i + 1) * m);

            List<Point> next = new ArrayList<Point>();
            next.addAll(l.subList(begin, end));
            groups.add(next);
        }

        for (List<Point> group : groups) {
            grahamConvexHull.convexHull(group);
        }

        List<Point> result = new ArrayList<Point>();
        result.add(min);

        for (int k = 0; k < m; k++) {
            Point current = result.get(k);

            Point next = binaryMaxSearch(current, groups.get(0));
            for (int i = 1; i < groupsCount; i++) {
                Point candidate = binaryMaxSearch(current, groups.get(i));
                if (Orientation.ABOVE == D2Util.getOrientation(current, candidate, next)) {
                    next = candidate;
                }
            }

            if (next.equals(min)) {
                return result;
            } else {
                result.add(next);
            }
        }

        return null;
    }

    private int correctIndex(List<Point> l, int index) {//l must contain at least 1 element
        index = index % l.size();
        if (index < 0) {
            index += l.size();
        }
        return index;
    }

    private int getMax(Point p, List<Point> l, int ... indexes) {
        int result = indexes[0];
        for (int i = 1; i < indexes.length; i++) {
            if (Orientation.ABOVE == D2Util.getOrientation(p, l.get(indexes[i]), l.get(result))) {
                result = indexes[i];
            }
        }
        return result;
    }

    private Point binaryMaxSearch(Point p, List<Point> conv) {//conv contains at least 1 element
        int n = conv.size();
        if (1 == n) {
            return conv.get(0);
        }
        int k = (int)log2(n);
        int r = getMax(p, conv, 0, (int)Math.pow(2, k) - 1);
        for (int i = k - 1; i >=0; i--) {
            int leftChild = correctIndex(conv, r - (int)Math.pow(2, i));
            int rightChild = correctIndex(conv, r + (int)Math.pow(2, i));
            r = getMax(p, conv, r, leftChild, rightChild);
        }
        return conv.get(r);
    }

    private double log2( double x ) {
        return Math.log(x) / Math.log(2);
    }

}
